package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class _124_max_path_sum {
    
    /**
     * 1. 肯定是递归求
     * 2. 先求孩子的单条路径最大值
     * 3. 声明全局最大路径和，递归进行比较
     * 4. 两个孩子的单条路径最大值和自己的和，与 max 进行比较，更新 max
     * 5. 单条路径最大值，至少一个节点，妈逼的怎么求？
     * 6. 自定向下多次重复计算，使用 map 记录
     *
     * 真几把恶心
     * 写的跟狗屎一样，居然通过了！
     *
     * */
    Map<TreeNode, Integer> childSumMap = new HashMap<>();
    int max = Integer.MIN_VALUE;
    public int maxPathSum2(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(0, getSum(root.left));
        int right = Math.max(0, getSum(root.right));
        max = Math.max(max, root.val + left + right);
        maxPathSum2(root.left);
        maxPathSum2(root.right);
        return max;
    }
    int getSum(TreeNode node) {
        if (node == null) return 0;
        if (childSumMap.containsKey(node))
            return childSumMap.get(node);
        int left = getSum(node.left);
        int right = getSum(node.right);
        int max = Math.max(node.val, Math.max(left, right) + node.val);
        childSumMap.put(node, max);
        return max;
    }
    
    /**
     * 我思路和答案差不多
     * 就是不知道怎么写成了这样子
     *
     * 就像大家都是人，有些人生出来的孩子是三体综合征
     *
     * */
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }
    int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));
        res = Math.max(res, node.val + left + right);
        return node.val + Math.max(left, right);
    }
    
}
